/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 字符串洗牌
 * 每个字符串使用二叉树进行表示，字符串翻洗主要指的是叶子节点的翻洗
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class ScrambleString {
  public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        if(s2.length()!=n){
            return false;
        }
        //使用三维数组记录子问题的结果 dp[i][j][len]代表从字符s1[i]开始和从字符s2[j]开始长度各为i+1的两个子串是否互为翻洗后的字符串
        boolean dp[][][] = new boolean[n][n][n];
        //初始化长度为1
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j][0] = s1.charAt(i)==s2.charAt(j);
            }
        }
        //计算长度为len的情况
        for(int len=1;len<n;len++){
            for(int i=0;i+len<n;i++){
                for(int j=0;j+len<n;j++){
                    for(int k=0;k<len;k++){
                        if((dp[i][j][k] && dp[i+k+1][j+k+1][len-1-k])
                                || (dp[i][j+len-k][k] && dp[i+k+1][j][len-1-k])){
                            dp[i][j][len] = true;
                            break;
                            //只要找出符合一种条件即可
                        }
                    }
                }
            }
        }
        return dp[0][0][n-1];
    }
  public static void main(String[] args) {
      ScrambleString scrambleString = new ScrambleString();
    String s1 = "girl";
    String s2 = "igrl";
    System.out.println(scrambleString.isScramble(s1, s2));
    String s3 = "gril";
    System.out.println(scrambleString.isScramble(s1, s3));
    
}
}
